1. Technical Field
The invention relates to processing images. More particularly, the invention relates to reducing the computational cost of a two-dimensional linear convolution applied in image processing techniques such as scaling, smoothing or sharpening.
2. Description of the Prior Art
When scaling a binary image, it is necessary to resolve any discrepancy between the input resolution and the output resolution. For example, in facsimile imaging the original images are transmitted at a standard resolution, typically 203 dots per inch ("dpi") in the row direction and 98 dpi in the column direction. The images are then printed at the printer resolution, e.g. 300 dpi in both the row and column directions. Another example of binary imaging involves font scaling. For example, when a 12 point font at 300 dpi is to be used as a 24 point font and printed on a 600 dpi printer, the original image must be scaled by a factor of four.
One approach to image scaling is to apply piecewise polynomial interpolation such as B-splines, as proposed in R. V. Klassen, R. H. Bartels, Using B-splines for Re-Sizing Images, University of Waterloo, Department of Computer Science, Technical Report, 1986. However, such approach has not proven satisfactory.
There are at least two barriers that prevent practical application of the Klassen and Bartels interpolation technique for image scaling in the industry. The first barrier concerns the quality of the result. Under some conditions, interpolation schemes give rise to a quantization errors, such that the image stroke width is not preserved after image scaling. For example, a quantization error problem embedded in all piecewise polynomial interpolants for scaling was reported in I. E. Abdou and K. Y. Wong, Analysis of Linear Interpolation Schemes for Bi-Level Image Applications, IBM J. Res. Develop., V. 26, No. 6, pp. 667-680, November, 1982.
A novel solution to this first barrier, the "quanfization error problem," was presented in Yen, Binary Image Scaling by Piecewise Polynomial Interpolation, U.S. Pat. No. 5,627,953, issued May 6, 1997 (U.S. patent application Ser. No. 08/286,561, filed Aug. 5, 1994), incorporated by reference as a part of this application. The fundamental idea of the Yen scaling algorithm is to treat the original image as three-dimensional data. The horizontal and vertical dimensions of the image are represented by the variables X and Y, respectively, and the intensity of the image is represented by the variable Z. The three dimensional data is then fitted to a piecewise polynomial (spline) surface. Re-sampling on this fitted surface produces the scaled image in gray scale. A final step of thresholding quantizes the gray scale into a binary result
The second barrier to the practical application of the interpolation technique is the computational complexity required, particularly for large scaling factors with high degree interpolants. It was determined by the inventors herein that the Yen spline algorithm produces high quality result in scaling binary text, especially for the large scaling factors encountered in printing on large format printers. However, the computations are enormously complex.
In Binary Image Scaling by Piecewise Polynomial Interpolation, Yen uses a convolution step in an interpolation technique for image scaling. Two dimensional linear convolutions are commonly used in digital image processing for image smoothing, sharpening and scaling. (See, for example, Jain, "Fundamentals of Digital Image Processing," Prentice Hall, 1989). The computational complexity of this type of scaling method is determined by the image size, the scaling factors, N.sub.h in horizontal direction and N.sub.v in vertical direction, and the degree of the interpolant, K.sub.h in horizontal direction and K.sub.v in vertical direction. The convolution weights require N.sub.h .multidot.N.sub.v weight tables, each weight table having K.sub.h .multidot.K.sub.v entries.
For example, FIG. 1 illustrates scaling an image by a factor of three in both horizontal and vertical directions by a bi-cubic (order four) B-spline interpolant. The four by four input pixel window's 14 dimensions are determined by the order of the interpolant.
An input pixel 10 is surrounded by neighboring pixels 12. When scaled by a factor of three in both horizontal and vertical directions, each input pixel 10 is scaled into an array 20 of nine output pixels. The number of output pixels (nine) represents the product of the horizontal (three) and vertical (three) scaling factors.
Each output pixel has an associated weight function. This weight function is dependent both on the degree of the interpolant and on the scaling factor. In Binary Image Scaling by Piecewise Polynomial Interpolation, Yen implements the weight function as convolution kernels. FIG. 2 is a table of convolution kernels for scaling by a factor of three with a bi-cubic uniform polynomial B-spline tensor product surface. The derivation of these convolution kernels is in accordance with the teachings of Yen, cited above. Each of the nine convolution kernels is a matrix having sixteen entries. For example, the matrix 22 is the convolution kernel representing the weight function for output pixel 24.
The convolution step to calculate output pixel 24 is the entry-by-entry multiplication of a matrix 26 representing the input pixel window with the convolution kernel matrix, ie 22, representing the appropriate weight function for each pixel in the window. In FIG. 1, the matrix 26 represents each shaded entry 18 of the input pixel window by the value one and each light entry 16 by the value zero. The multiplication of the input pixel window matrix 26 with the weight function matrix 22 produces a gray scale value of the resulting output pixel. To achieve the final binary result representing the output pixel, a thresholding step is used.
The Yen convolution kernels exhibit subtle mathematical properties which are related to the complexity of the interpolation process. For example, the value zero entries 28 in convolution kernel matrix 22 indicate that the pixels in the bottom row 30 and the right most column 32 of the input pixel window are not used as part of the input pixel weighting process to derive output pixel 24. This is called the locality property.
Various symmetries are observed both within and across the table of sample convolution kernels. Such symmetries include kernels having symmetric rows or columns of repeating vectors in transposes, reflects or permutations.
Each convolution kernel matrix in FIG. 2 has one entry having a dominating weight. By comparison, the corner entries of the kernels usually have much smaller, insignificant weights. Therefore, some of the input pixels that have smaller weights can be ignored in the convolution step without significantly affecting the output result. This is called the dominancy property.
In one extreme approach, each output pixel is processed by multiplying each of the K.sub.h by K.sub.v input pixels, entry by entry, with the weight table. The K.sub.h *K.sub.v products are added, and a thresholding step is performed on the sum. The total computational cost of this approach is K.sub.h *K.sub.v multiplications plus K.sub.h *K.sub.v -1 additions and 1 comparison, all in double precision floating point arithmetic, for each output pixel.
For example, scaling a letter-sized, 300 dpi (dot-per-inch) image by 4 to a 600 dpi output, is effectively equivalent to scaling the image by 8 times in both directions by a bi-septimal (degree 7, order 8) B-spline interpolant. The total computation for this scaling operation is approximately 65 Giga Floating Point Operations. Using a 40 MFLOPS (Million Floating Point Operations Per Second) processor, this scaling process requires approximately 30 minutes of CPU time.
In another extreme approach, a table look-up scheme is used to speed up the convolution step. Every possible resulting product of the multiplication of each of the input pixels by the weight function is pre-calculated and stored in a table. The thresholding value is also pre-determined. The scaling process is performed by matching patterns of the input pixels and producing output pixels by table lookup.
Using a table lookup scheme, the time complexity is linear in relation to the output image size. The space complexity is related exponentially to the degree of the interpolant. If the output is binary, the lookup table size is 2.sup.(K.sbsp.h.sup..multidot.K.sbsp.v.sup.) .multidot.(N.sub.h .multidot.N.sub.v) bits. Some advantageous properties of B-splines, such as locality, symmetry and dominancy, can be utilized to reduce the table size. For example, when a table lookup scheme to scale by 3 with a bi-cubic B-spline interpolant, the lookup table size is reduced from 72 KB using the above-described convolution technique, to approximately 7 KB.
However, when using a higher order interpolant and larger scaling factors, the lookup table size increases dramatically to an impractical size. In the example discussed above, scaling an image 8 times in both directions by a bi-septimal B-spline interpolant, 2.sup.67 bytes are required.
It would therefore be an advantage to substantially reduce computational cost of image processing techniques as compared to the prior art. It would be yet another advantage to balance the time and space complexities to provide a practical application.